AtCoder Beginner Contest 139 - E - League
https://gyazo.com/01d5e8d0690517630a41a34e736fd4a6
考えたこと
純粋に考えれば、1日目から最大でN(N-1)/2日までをみていけば良いかな。
全ての試合が終了したら、終わりでいいし
1日も試合が開催できない日があれば、-1を出力でいいかと
各選手が今どれだけ試合を消化したかを管理するvectorを用意しておいて、試合を紹介したら、そこを++する感じで
で選手は1日1試合しかできないから、対戦相手がすでに試合してたら、それは試合できないって感じで
これ最悪計算量が $ \frac{N \times N \times (N-1)}{2} でほぼほぼ$ N^3なので、間に合わないかな。。と思って出したらTLEになった
code: 出したコード.cpp
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) #define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i) #define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i) #define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i) template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
int main() {
int n; cin >> n;
rep(i,1005) rep(j, 1005) aij = -1; rep(i,1005) finishedi = 0; // 入れる
rep(i, n) rep(j, n-1) cin >> aij; bool flag = true;
int ans = 0;
while(flag) {
int match_game = 0;
bool all_finish = true;
vector<bool> today(n, false);
rep(i, n) {
//cout << i << "は終わった" << endl;
continue;
}
all_finish=false;
int rival = ai[finishedi]-1; //cout << i << ":" << rival << endl;
match_game++;
//cout << i << " : " << rival << endl;
} else {
//cout << rival << "は本日すでに対戦ずみ" << endl;
}
}
}
// 全てが終わったら終了
if(all_finish) {
cout << ans << endl;
return 0;
}
// 1つもゲームが行われかったらNG
if(match_game == 0) {
cout << -1 << endl;
return 0;
}
// 1日終わり
ans++;
}
}
解説をみて
https://www.youtube.com/watch?v=UWbGRhF3Ozw
解法が2種類あるらしい、
Queueを使って、$ N^2logNに計算量を落とす方法
グラフを使う方法
Queueを使って、$ N^2に計算量を落とす方法
$ \frac{N \times (N-1)}{2} 日をみるのは変わらない。1日の中で毎回Nループを回すのが問題
ここを落とす。
毎日全員をチェックする必要はないはず。
例えば、選手1が2,3,4,5で選手5が1,2,3,4 の順で試合しないといけない場合、選手5は選手1が2,3,4との試合を終えたあとで試合できるので、初日にできるかチェックしたあと、少なくとも2日はチェックが不要なはず.
もう少し考えると、初日に組み合わせをチェックしたら、翌日にチェックするのは、前日に試合を行った人たちだけでいいはず(その人たち以外はある意味でデッドロックみたいな状態なので)
stackでもqueueでもvectorでもなんでもいいけど、2つ用意して今日試合できるペア、明日試合できるペアを管理することで、初日を除けば、1日あたりの計算量がその日に行える試合分に減らせる
最終的にループ内でチェックする最大数は最大試合数と同じになるので、$ \frac{N \times (N-1)}{2} になり
日数と掛け算でなく、足し算になるので, 計算量が$ N^2になる
解説ではvectorでやってましたが、重複処理などが面倒になります。
ここでは、ある選手の次の対戦相手を管理するコンテナと、今日試合するペアのコンテナの2つが必要になります。
ある選手の次の対戦相手の管理は、標準入力で受け付けた順で取り出すだけでいいので、シンプルなFIFOができるQueueで十分でしょう
今日試合するペアの管理は、中の順番は考慮不要であることがわかります。必要なのは、重複した値を入れたくないということだけなので、setで良いと思います。
https://gyazo.com/70d61e54a67cc3055ad34c87b7b213e3
code: setとqueueを使う版.cpp
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) #define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i) #define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i) #define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i) template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
typedef pair<int,int> P;
int main() {
int n; cin >> n;
vector<queue<int>> a(n, queue<int>());
rep(i, n) rep(j, n-1) {
int tmp;
cin >> tmp;
}
vector<bool> mached(n, false);
set<P> q;
if(ai.size() == 0) return; int j = ai.front(); // 次の対戦相手はQueueの先頭 if(aj.size() == 0) return; // 対戦相手が全て消化してたらNG(ないと思うけど) if(aj.front() == i) { // 対戦相手の次の相手も同じだったら、その試合は行えるので、setに追加する P p(i, j);
if(p.second < p.first) swap(p.first, p.second); // UniqueにするためにPairのfirstを小さい方の値にする
q.insert(p);
}
};
// 初日分を全てチェック
rep(i, n) check(i);
int ans = 0;
while(q.size() > 0) {
ans++;
set<P> prevQ;
swap(prevQ, q);
// 今日実施できる試合を消化する
for(P p : prevQ) {
int i = p.first, j = p.second;
}
for(P p : prevQ) {
int i = p.first, j = p.second;
// 次の日にできる試合をチェックする
check(i);
check(j);
}
}
rep(i, n) {
puts("-1");
return 0;
}
}
cout << ans << endl;
return 0;
}
おまけ
Twitterで検索してたら、TLEは1ケースだけなので、最悪計算量のはず。その時はN(N-1)/2を出力すれば通ったっていうのみて真似して出したら確かに通った。ちょっとずるい方法を覚えてしまった。(使えるケース少ないだろうけど)